class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2,
                                       int k) {
        int n = nums1.size();
        int m = nums2.size();
        vector<vector<int>> res;
        priority_queue<tuple<int, int, int>> pq;
        // 最小的肯定是0，0,并且我们要形成最小堆
        // 所以要将-(nums[i]+nums[j])
        pq.push({-(nums1[0] + nums2[0]), 0, 0});
        while (res.size() < k) {
            // 获得最小堆堆顶的三元组
            auto [val, i, j] = pq.top();
            res.push_back({nums1[i], nums2[j]});
            pq.pop();
            // 规定:[i,j](j == 0)能插入[i+1,j]和[i,j+1]
            //[i,j](j != 0)只能插入[i,j+1];
            if (j == 0 && i + 1 < n) {
                pq.push({-(nums1[i + 1] + nums2[j]), i + 1, j});
            }
            if (j + 1 < m) {
                pq.push({-(nums1[i] + nums2[j + 1]), i, j + 1});
            }
        }
        return res;
    }
};